package 数据结构专栏.C_排序算法;

import java.util.Arrays;

/**
 * @Title 重要：二分查找
 * https://blog.csdn.net/allway2/article/details/115119507
 * @Author zhengqiang.tan
 * @Date 2021/4/20 8:35 AM
 * <p>
 * <p>
 * Java提供了三种实现二分查找的方式：
 * <p>
 * 1.使用迭代方法
 * 2.使用递归方法
 * 3. 使用Arrays.binarySearch（）方法。
 */
public class 二分查找 {

    public static void main(String[] args) {

        int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90,100};
        System.out.println("The input Array : " + Arrays.toString(arr));
        int key = 30;

        System.out.println(binary_Search_iterator(arr, key));


//        int result = Arrays.binarySearch(intArray, key);
//        if (result < 0)
//            System.out.println("\nKey is not found in the array!");
//        else
//            System.out.println("\nKey is found at index: " + result + " in the array.");
    }

    /**
     * 递归方式查找元素的位置
     */
    public static int binary_Search(int[] arr, int low, int high, int key) {
        if (high >= low) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == key) {
                return mid;
            }
            if (arr[mid] > key) {
                return binary_Search(arr, low, mid - 1, key);
            } else {
                return binary_Search(arr, mid + 1, high, key);
            }
        }
        return -1;
    }


    /**
     * 迭代方式
     */
    public static int binary_Search_iterator(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (key < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;

    }


}
